//
//  Problem1482.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1482. 制作 m 束花所需的最少天数
 给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

 现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
 花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

 示例 1：
     输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
     输出：3
     解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
     现在需要制作 3 束花，每束只需要 1 朵。
     1 天后：[x, _, _, _, _]   // 只能制作 1 束花
     2 天后：[x, _, _, _, x]   // 只能制作 2 束花
     3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3
 示例 2：
     输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
     输出：-1
     解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。
 示例 3：
     输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
     输出：12
     解释：要制作 2 束花，每束需要 3 朵。
     花园在 7 天后和 12 天后的情况如下：
     7 天后：[x, x, x, x, _, x, x]
     可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
     12 天后：[x, x, x, x, x, x, x]
     显然，我们可以用不同的方式制作两束花。
 示例 4：
     输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
     输出：1000000000
     解释：需要等 1000000000 天才能采到花来制作花束
 示例 5：
     输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
     输出：9
 提示：
     bloomDay.length == n
     1 <= n <= 10^5
     1 <= bloomDay[i] <= 10^9
     1 <= m <= 10^6
     1 <= k <= n
 */
@objcMembers class Problem1482: NSObject {
    func solution() {
//        print(minDays([1,10,3,10,2], 3, 1))
//        print(minDays([1,10,3,10,2], 3, 2))
//        print(minDays([7,7,7,7,12,7,7], 2, 3))
//        print(minDays([1000000000,1000000000], 1, 1))
//        print(minDays([1,10,2,9,3,8,4,7,5,6], 4, 2))
        print(minDays([62,75,98,63,47,65,51,87,22,27,73,92,76,44,13,90,100,85], 2, 7))
    }
    
    /*
     二分法
     首先确定left和right：
     left： 数组中的最小值，因为：有可能都是同一天成熟
     right：数组中的最大值，等到最后一天，肯定所有的都成熟了
     然后通过left和right计算出中间天数mid，看看在第mid天时，能形成几束花n
     n >= m, 说明mid满足要求，但我们求的是最小值，r=mid-1
     n < m, 说明mid不满足，l=mid+1
     
     */
    func minDays(_ bloomDay: [Int], _ m: Int, _ k: Int) -> Int {
        if m * k > bloomDay.count {
            return -1
        }
        var l = Int.max
        var r = Int.min
        for d in bloomDay {
            l = min(l, d)
            r = max(r, d)
        }
        
        var mid = 0
        var num = 0
        while l <= r {
            mid = l + (r - l) >> 1
            // 获取第mid天后，能够获得的花束的个数
            num = getNum(bloomDay, mid, k)
            if num >= m {    // 获得个数满足需求，但我们求最小值
                r = mid - 1
            } else {         // 获得个数满足不需求
                l = mid + 1
            }
        }
        return l
    }
    
    func getNum(_ bloomDay: [Int], _ d: Int, _ k: Int) -> Int {
        var day = 0
        var l = 0
        for ni in bloomDay {
            if ni <= d {    // 在第d天时，ni成熟了
                l += 1
                if l == k { // 满足了形成一束花
                    day += 1
                    l = 0
                }
            } else {        // 因为要求连续，这里打断了连续性
                l = 0
            }
        }
        return day
    }
}
